import java.util.ArrayDeque;
import java.util.Deque;

public class MaxSlidingWindow {
    // leetcode 滑动窗口最大值
    // https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int len = nums.length;
        int[] ret = new int[len-k+1];
        int index = 0;
        for (int i = 0; i < len; i++) {
            while (!deque.isEmpty() && deque.peek() <= i-k) {
                deque.poll();
            }
            // 维护队列中的单调性 对头->对尾递增
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);
            // 当窗口大小达到k的时候，统计数据
            if (i >= k-1) {
                ret[index++] = nums[deque.peek()];
            }
        }
        return ret;
    }
}
